package com.julius.design.suanfa.tree;

import java.util.Stack;

/**
 * @author julius
 * @date 2021-10-26 上午 11:01
 * <p>
 *      镜像树  0 <= 节点个数 <= 1000
 *      https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
 *
 *              4
 *            /   \
 *          2      7
 *         / \    / \
 *        1   3  6   9
 * </p>
 */
public class MirrorTree {

    /**
     * 镜像翻转树 方法:递归回溯   自下向上交换
     * @param node 带翻转节点
     * @return TreeNode
     */
    public static TreeNode mirrorTree(TreeNode node){
        if(node == null){
            return null;
        }
        //翻转后的左子树
        TreeNode left = mirrorTree(node.left);
        //翻转后的右子树
        TreeNode right = mirrorTree(node.right);
        //交换
        node.left = right;
        node.right = left;
        return node;
    }

    /**
     * 辅助栈进行交换 ：：： 自上向下的交换
     * 先将节点的左右子树加入栈，然后交换左右子树，然后再去处理左右子树的左右子树
     * @param root
     * @return
     */
    public static TreeNode mirrorTree2(TreeNode root) {
        //二叉树镜像。题意理解就是将一个树的左右子树进行互换位置
        //2. 辅助栈，利用栈的先进后出原则，其实说是一个深度优先遍历算法DFS 前序遍历算法
        if(root == null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            //弹出第一个节点
            TreeNode node = stack.pop();

            //判断是否有左右子树,如果有，就加入栈
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
            TreeNode temp = node.left;
            //交换左右子树
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
}
